﻿/*
题目: 青蛙过河

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

https://leetcode.cn/problems/frog-jump/description/?envType=study-plan-v2&envId=2024-spring-sprint-100
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        if (stones[1] != 1)         return false;

        // dp[i] 表示跳到 i 个石块 有多少中单位的跳法
        vector<unordered_set<int>> dp(n);

        dp[1].insert(1);
        for (int i = 1; i < n - 1; i++) {
            // 历史跳到 i 有多少种步数
            for (int his : dp[i]) {
                for (int k = max(his - 1, 1); k <= his + 1; k++) {
                    int idx = bin_serach(stones, i + 1, stones[i] + k);
                    if (idx != -1) {
                        dp[idx].insert(k);
                    }
                }
            }
        }

        return !dp[n - 1].empty();
    }

    int bin_serach(vector<int>& nums, int start, int tar) {
        int left = start, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] >= tar) {
                right = mid - 1;
            }
            else {  // nums[mid] < tar
                left = mid + 1;
            }
        }
        return left == nums.size() || nums[left] != tar ? -1 : left;
    }
};
